#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

const int N=5e5+10;

struct node{
    int l,r;
    int sum,lmax,rmax,tmax;
}tr[N * 4];
int n,m,w[N];

void pushup(node &t,node &l,node &r)
{
    t.sum=l.sum+r.sum;
    t.lmax=max(l.lmax,l.sum+r.lmax);
    t.rmax=max(r.rmax,r.sum+l.rmax);
    t.tmax=max(max(l.tmax,r.tmax),l.rmax+r.lmax);
}

void pushup(int u)
{
    pushup(tr[u], tr[u<<1], tr[u<<1|1] );
}

void build(int u,int l,int r)
{
    if(l == r) tr[u]={r,r,w[r],w[r],w[r],w[r]};
    else
    {
        tr[u]={l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

node query(int u,int l,int r)
{
    if(l <= tr[u].l && tr[u].r <= r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) return query(u<<1,l,r);
        else if(mid < l) return query(u<<1|1,l,r);
        else
        {
            node left = query(u<<1,l,r);
            node right = query(u<<1|1,l,r);
            node res;
            pushup(res,left,right);
            return res;
        }
    }
}

void modify(int u,int x,int v)
{
    if(tr[u].l == x && tr[u].r == x) tr[u]={x,x,v,v,v,v};
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        pushup(u);
    }
}

int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d",&w[i]);

    build(1,1,n);

    while(m--)
    {
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k == 1)
        {
            if(x>y) swap(x,y);
            cout<<query(1,x,y).tmax<<'\n';
        }
        else
        {
            modify(1,x,y);
        }
    }
    return 0;
}
